package com.atguigu.search;

import com.atguigu.sort.SelectSort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author shkstart
 * @create 2021-08-16 1:07
 */
//二分查找算法适用于分布不均匀的查找表
//二分查找需要查找的次数比较多，效率不大
public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {3, 22, -6, 89, 89, 89, 54, 677, 0};

        Arrays.sort(arr);
//        int index = binarySearch(arr, 0, arr.length - 1, 89);
//        System.out.println(index);
//        System.out.println(Arrays.toString(arr));
        List<Integer> list = binarySearch2(arr, 0, arr.length - 1, 89);
        System.out.println(list);

    }

    //二分查找法
    public static int binarySearch(int[] arr, int left, int right, int findVal) {


        //找不到时
        if (left > right) {
            System.out.println("找不到对应的数字！");
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (midVal > findVal) {
            return binarySearch(arr, left, mid - 1, findVal);
        } else if (midVal < findVal) {
            return binarySearch(arr, mid + 1, right, findVal);
        } else {
            return mid;
        }

    }


//    相同值时，特殊的二分查找法
    public static ArrayList<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {


        //找不到时
        if (left > right) {
            System.out.println("找不到对应的数字！");
            return new ArrayList<>();
        }

        int mid = (left + right) / 2;
        int midVal=arr[mid];

        if (midVal > findVal) {
            return binarySearch2(arr, left, mid-1, findVal);
        } else if (midVal < findVal) {
            return binarySearch2(arr, mid+1, right, findVal);
        } else {
            // * 思路分析
            //	 * 1. 在找到mid 索引值，不要马上返回
            //	 * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
            //	 * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
            //	 * 4. 将Arraylist返回
            //	 */
            //创建集合
            ArrayList<Integer> indexresult = new ArrayList<>();
            //左边扫描
            int temp=mid-1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    break;
                }

                indexresult.add(temp);
               temp--;
            }
            //加上中间
            indexresult.add(mid);

            //扫描右边
            temp=mid+1;
            while (true) {
            if (temp > arr.length-1 || arr[temp] != findVal) {
                break;
            }

            indexresult.add(temp);
            temp++;
        }
        return indexresult;
        }

    }
}

